1845C - Strong Password - CodeForces Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <map>


using namespace std;
using ll = long long;


bool solve() {
  string s;
  int m;
  string l,r;
  cin>>s>>m;
  cin>>l>>r;
  int n = s.length();
  map<char,vector<int>> ind;
  for (int i=0; i<n; i++) {
    ind[s[i]].push_back(i);
  }

  // from [l[i],r[i]], greedily pick c that is farthest
  // right. this minimizes the chance of completing
  // the subsequence. this is the best we can do
  // at any index i.
  
  int at = -1;
  for (int i=0; i<m; i++) {
    int to = -1;
    for (char c=l[i]; c<=r[i]; c++) {
      auto it = upper_bound(ind[c].begin(), ind[c].end(), at);
      if (it == ind[c].end()) return true;
      to = max(to, *it);
    }
    at = to;
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

  int t;
  cin>>t;
  while (t--) {
    cout<<(solve() ? "YES" : "NO")<<"\n";
  }
  
  return 0;
}